package data;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

class AllOne {

    HashMap<String , Integer> value;

    HashMap<Integer, DLinkNode> nodes;

    DLinkNode head,tail;

    static class DLinkNode {
        int val;
        Set<String> keys = new HashSet<>();
        DLinkNode next;
        DLinkNode pre;
        DLinkNode(int val) {
            this.val = val;
        }
    }

    /** Initialize your data structure here. */
    public AllOne() {
        value = new HashMap<>();
        nodes = new HashMap<>();
        head = new DLinkNode(0);
        tail = new DLinkNode(0);
    }

    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        Integer val = value.get(key);
        if(val == null) {
            value.put(key, 1);
            DLinkNode node = nodes.get(1);
            if(node == null) {
                node = new DLinkNode(1);
                nodes.put(1, node);
                node.next = head.next;
                node.pre = head;
                if(head.next != null) {
                    head.next.pre = node;
                }
                head.next = node;

                if (tail.pre == null || tail.pre.val < 1) {
                    tail.pre = node;
                    node.next = tail;
                }
            }
            node.keys.add(key);
        } else {
            value.put(key, val+1);
            DLinkNode node = nodes.get(val);
            // 删除旧的节点上的key
            node.keys.remove(key);

            if(node.keys.size() == 0) {
                node.pre.next = node.next;
                node.next.pre = node.pre;
                node = node.pre;
                nodes.remove(val);
            }

            DLinkNode newNode = nodes.get(val+1);
            if (newNode == null){
                newNode = new DLinkNode(val+1);
                nodes.put(val+1, newNode);
                newNode.pre = node;
                newNode.next = node.next;
                if(node.next != null) {
                    node.next.pre = newNode;
                }
                node.next = newNode;
                if (tail.pre == null || tail.pre.val < val+1) {
                    tail.pre = newNode;
                    newNode.next = tail;
                }
            }
            newNode.keys.add(key);
        }
    }

    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        Integer val = value.get(key);
        if(val == null) {
            return;
        }
        // 先删除旧key
        DLinkNode node = nodes.get(val);

        node.keys.remove(key);
        if(node.keys.isEmpty()) {

            node.pre.next = node.next;
            node.next.pre = node.pre;
            node = node.next;
            nodes.remove(val);
        }

        if(val == 1) {
            value.remove(key);
        } else {
            value.put(key, val-1);
            DLinkNode newNode = nodes.get(val-1);
            if(newNode == null) {
                newNode = new DLinkNode(val-1);
                nodes.put(val -1 , newNode);
                newNode.next = node;
                newNode.pre = node.pre;

                if(node.pre != null) {
                    node.pre.next = newNode;
                }
                node.pre = newNode;
//
//                if(node.next != null) {
//                    node.next.pre = newNode;
//                }

                node.pre = newNode;
            }
            newNode.keys.add(key);
        }

    }

    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        if(tail == null ||tail.pre == null) {
            return "";
        }
        return tail.pre.keys.iterator().next();
    }

    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        if(head == null || head.next == null) {
            return "";
        }
        return head.next.keys.iterator().next();
    }



    public static void main(String[] args) {
        AllOne test =new AllOne();
        test.inc("hello");
        test.inc("hello");
        test.inc("hello");
        test.inc("world");
        test.inc("world");
        test.dec("world");
        System.out.println(test.getMaxKey());
        System.out.println(test.getMinKey());
        test.inc("hello");
        test.inc("lettcode");
        System.out.println(test.getMaxKey());
        System.out.println(test.getMinKey());
        test.dec("hello");
        test.dec("hello");
        test.dec("hello");
        System.out.println(test.getMaxKey());
    }
}
